package Leetcode;

/**
 * 最小路径和
 * <p>
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 * <p>
 * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 * 输出：7
 * 解释：因为路径 1→3→1→1→1 的总和最小。
 */
public class 力扣64_最小路径和 {
    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};

        minPathSum3(grid, grid.length, grid[0].length, 0, 0, 0);
        System.out.println(minPath3);

        minPathSum4(grid, grid.length, grid[0].length, 0, 0, grid[0][0]);
        System.out.println(minPath4);

        System.out.println(minPathSum2(grid));
    }

    /**
     * 使用临时二维数组存储数据
     */
    public static int minPathSum(int[][] grid) {
        int x = grid.length;
        int y = grid[0].length;
        int[][] temp = new int[x][y];
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                int curVal = grid[i][j];
                if (i > 0 && j > 0) {
                    // 上边和左边都有值
                    int preXVal = curVal + temp[i - 1][j];
                    int preYVal = curVal + temp[i][j - 1];
                    temp[i][j] = Math.min(preXVal, preYVal);
                } else if (i > 0) {
                    // 上边有值
                    int preXVal = curVal + temp[i - 1][j];
                    temp[i][j] = preXVal;
                } else if (j > 0) {
                    // 左边有值
                    int preYVal = curVal + temp[i][j - 1];
                    temp[i][j] = preYVal;
                } else {
                    // 上边和左边都没值 只有[0][0]一种情况
                    temp[i][j] = curVal;
                }
            }
        }
        return temp[x - 1][y - 1];
    }

    /**
     * 优化使用临时一维数组存储
     */
    public static int minPathSum1(int[][] grid) {
        int x = grid.length;
        int y = grid[0].length;
        int[] temp = new int[y];
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (i > 0 && j > 0) {
                    // 上边和左边都有值
                    temp[j] = grid[i][j] + Math.min(temp[j], temp[j - 1]);
                } else if (i > 0) {
                    // 上边有值
                    temp[j] = grid[i][j] + temp[j];
                } else if (j > 0) {
                    // 左边有值
                    temp[j] = grid[i][j] + temp[j - 1];
                } else {
                    // 上边和左边都没值 只有[0][0]一种情况
                    temp[j] = grid[i][j];
                }
            }
        }
        return temp[y - 1];
    }

    /**
     * 优化 不使用临时数组存储 使用本身数组存储
     */
    public static int minPathSum2(int[][] grid) {
        int x = grid.length;
        int y = grid[0].length;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (i > 0 && j > 0) {
                    // 上边和左边都有值
                    grid[i][j] = grid[i][j] + Math.min(grid[i - 1][j], grid[i][j - 1]);
                } else if (i > 0) {
                    // 上边有值
                    grid[i][j] = grid[i][j] + grid[i - 1][j];
                } else if (j > 0) {
                    // 左边有值
                    grid[i][j] = grid[i][j] + grid[i][j - 1];
                }
            }
        }
        return grid[x - 1][y - 1];
    }

    static int minPath3 = Integer.MAX_VALUE;

    public static void minPathSum3(int[][] grid, int maxX, int maxY, int x, int y, int preSum) {
        if (x >= maxX || y >= maxY) {
            return;
        }
        int curSum = grid[x][y] + preSum;
        if (x == maxX - 1 && y == maxY - 1) {
            minPath3 = Math.min(minPath3, curSum);
            return;
        }
        minPathSum3(grid, maxX, maxY, x + 1, y, curSum);
        minPathSum3(grid, maxX, maxY, x, y + 1, curSum);
    }

    static int minPath4 = Integer.MAX_VALUE;

    public static void minPathSum4(int[][] grid, int maxX, int maxY, int x, int y, int sum) {
        if (x == maxX - 1 && y == maxY - 1) {
            minPath4 = Math.min(minPath4, sum);
            return;
        }
        if (x + 1 < maxX) {
            minPathSum4(grid, maxX, maxY, x + 1, y, sum + grid[x + 1][y]);
        }
        if (y + 1 < maxY) {
            minPathSum4(grid, maxX, maxY, x, y + 1, sum + grid[x][y + 1]);
        }
    }

}
